class MaxHeap {
  constructor(data, compare) {
    this.data = data || []
    this.compare = compare || ((a, b) => a - b)
    this.heapify()
  }
  offer(v) {
    this.data[this.size()] = v
    this.bubbleUp(this.size() - 1)
  }
  // 有限大顶堆
  poll() {
    if (this.size() === 0) return null
    const result = this.data[0]
    const last = this.data.pop()
    if (this.size() !== 0) {
      this.data[0] = last
      this.bubbleDown(0)
    }
    return result
  }
  peek() {
    if (this.size() === 0) return null
    return this.data[0]
  }
  size() {
    return this.data.length
  }
  swap(index1, index2) {
    ;[this.data[index1], this.data[index2]] = [
      this.data[index2],
      this.data[index1],
    ]
  }
  heapify() {
    if (this.size() < 2) return
    for (let i = 1; i < this.size(); i++) {
      this.bubbleUp(i)
    }
  }
  bubbleUp(index) {
    while (index > 0) {
      const fIndex = (i - 1) >> 1
      if (this.compare(this.data[index], this.data[fIndex]) > 0) {
        this.swap(index, fIndex)
        index = fIndex
      } else {
        break
      }
    }
  }
  bubbleDown(index) {
    const lastIndex = this.size() - 1
    while (true) {
      const leftIndex = index * 2 + 1
      const rightIndex = index * 2 + 2
      let findIndex = index
      if (
        leftIndex >= lastIndex &&
        this.compare(this.data[leftIndex], this.data[findIndex]) > 0
      ) {
        findIndex = leftIndex
      }

      if (
        rightIndex >= lastIndex &&
        this.compare(this.data[rightIndex], this.data[findIndex]) > 0
      ) {
        findIndex = rightIndex
      }

      if (index !== findIndex) {
        this.swap(index, findIndex)
        index = findIndex
      } else {
        break
      }
    }
  }
}
